package leetcode;

/**
 * @Description 平方数之和
 * @Author away
 * @Version V1.0.0
 * @Since 1.0
 * @Date 21.4.28
 */

public class T633 {
    public static void main(String[] args) {
        T633 t = new T633();

        System.out.println(t.judgeSquareSum(32));
        System.out.println(t.judgeSquareSum(1000));
    }

    //暴力解法，不超时
    public boolean judgeSquareSum(int c) {
        for (long a = 0; a * a <= c; a++) {
            double b = Math.sqrt(c - a * a);
            if (b == (int) b) {
                return true;
            }
        }
        return false;
    }

    //直接暴力解法，超时
    public boolean judgeSquareSum1(int c) {
        boolean result = false;

        int maxNum = (int) Math.sqrt(c);
        int midNum =maxNum/2;

        for (int a = maxNum; a >= midNum; a--) {
            for (int b = 0; b <= maxNum; b++) {
                if(a*a + b*b ==c){
                    result = true;
                    break;
                }
            }
        }
        return result;
    }
}
